{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Two Binary Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两棵二叉树： <code>root1</code> 和 <code>root2</code> 。</p>\n",
    "\n",
    "<p>想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，<strong>不为</strong> null 的节点将直接作为新二叉树的节点。</p>\n",
    "\n",
    "<p>返回合并后的二叉树。</p>\n",
    "\n",
    "<p><strong>注意:</strong> 合并过程必须从两个树的根节点开始。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/05/merge.jpg\" style=\"height: 163px; width: 600px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]\n",
    "<strong>输出：</strong>[3,4,5,5,4,null,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [1], root2 = [1,2]\n",
    "<strong>输出：</strong>[2,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两棵树中的节点数目在范围 <code>[0, 2000]</code> 内</li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-two-binary-trees](https://leetcode.cn/problems/merge-two-binary-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-two-binary-trees](https://leetcode.cn/problems/merge-two-binary-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,5]\\n[2,1,3,null,4,null,7]', '[1]\\n[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1 is None:\n",
    "            if t2 is None:\n",
    "                return None\n",
    "            else:\n",
    "                return t2\n",
    "        else:\n",
    "            if t2 is None:\n",
    "                return t1\n",
    "            \n",
    "        return TreeNode(t1.val + t2.val, self.mergeTrees(t1.left, t2.left), self.mergeTrees(t1.right, t2.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not t1:\n",
    "            return t2\n",
    "        if not t2:\n",
    "            return t1\n",
    "        head = t1\n",
    "        queue1 = [t1]\n",
    "        queue2 = [t2]\n",
    "        while queue1:\n",
    "            node1 = queue1.pop(0)\n",
    "            node2 = queue2.pop(0)\n",
    "            node1.val += node2.val\n",
    "            if node1.left and node2.left:\n",
    "                queue1.append(node1.left)\n",
    "                queue2.append(node2.left)\n",
    "            elif node2.left:\n",
    "                node1.left = node2.left\n",
    "            if node1.right and node2.right:\n",
    "                queue1.append(node1.right)\n",
    "                queue2.append(node2.right)\n",
    "            elif node2.right:\n",
    "                node1.right = node2.right\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # if t1 and t2:\n",
    "        #     t = TreeNode(t1.val + t2.val)\n",
    "        #     t.left = self.mergeTrees(t1.left, t2.left)\n",
    "        #     t.right = self.mergeTrees(t1.right, t2.right)\n",
    "        # else:\n",
    "        #     t = t1 if t1 else t2\n",
    "        # return t\n",
    "        \n",
    "        \"\"\"\n",
    "        非递归实现\n",
    "        https://leetcode.com/problems/merge-two-binary-trees/discuss/104429/Python-BFS-Solution\n",
    "        主要思路：\n",
    "        对于两棵树的同一位置的某个节点，\n",
    "        1：都有左右孩子节点      节点值直接相加\n",
    "        2: 都没有左右孩子节点    直接返回，检查下一个节点\n",
    "        3/4：一左一右，一右一左  对于不存在的孩子节点，新增一个val=0的节点，转换成情况1再相加\n",
    "        \"\"\"\n",
    "\n",
    "        if not (t1 and t2):\n",
    "            return t1 or t2\n",
    "        queue1, queue2 = collections.deque([t1]), collections.deque([t2])\n",
    "        while queue1 and queue2:\n",
    "            node1, node2 = queue1.popleft(), queue2.popleft()\n",
    "            if node1 and node2:\n",
    "                node1.val = node1.val + node2.val\n",
    "                if (not node1.left) and node2.left:\n",
    "                    node1.left = TreeNode(0)\n",
    "                if (not node1.right) and node2.right:\n",
    "                    node1.right = TreeNode(0)\n",
    "                queue1.append(node1.left)\n",
    "                queue1.append(node1.right)\n",
    "                queue2.append(node2.left)\n",
    "                queue2.append(node2.right)\n",
    "        return t1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if t1 is None and t2 is None:\n",
    "            return None\n",
    "        elif t1 is None and t2 is not None:\n",
    "            return t2\n",
    "        elif t1 is not None and t2 is None:\n",
    "            return t1\n",
    "        else:\n",
    "            t1.val = t2.val + t1.val\n",
    "            t1.left = self.mergeTrees(t1.left, t2.left)\n",
    "            t1.right = self.mergeTrees(t1.right, t2.right)\n",
    "            return t1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if (t2 is None): return t1\n",
    "        if (t1 is None): return t2\n",
    "        merged = TreeNode(t1.val + t2.val)\n",
    "        merged.left = self.mergeTrees(t1.left, t2.left)\n",
    "        merged.right = self.mergeTrees(t1.right, t2.right)\n",
    "        return merged\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if t1 and t2:\n",
    "            t1.val += t2.val\n",
    "            t1.left = self.mergeTrees(t1.left,t2.left)\n",
    "            t1.right = self.mergeTrees(t1.right,t2.right)\n",
    "            return t1\n",
    "        if t2:\n",
    "            return t2\n",
    "        if t1:\n",
    "            return t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \n",
    "        \n",
    "        if  t1 or t2:\n",
    "            v1,v2=0,0\n",
    "            t1l,t2l,t1r,t2r=None,None,None,None\n",
    "            if t1 :\n",
    "                v1=t1.val \n",
    "                t1l=t1.left\n",
    "                t1r=t1.right\n",
    "            if t2 :\n",
    "                v2=t2.val \n",
    "                v2=t2.val \n",
    "                t2l=t2.left\n",
    "                t2r=t2.right\n",
    "            tn=TreeNode(v1+v2)\n",
    "            tn.left=self.mergeTrees(t1l, t2l)\n",
    "            tn.right=self.mergeTrees(t1r, t2r)\n",
    "            return tn\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode):\n",
    "        if t1 and not t2:\n",
    "                return t1\n",
    "        if not t1 and t2:\n",
    "                return t2\n",
    "        if t1 and t2:\n",
    "                root = TreeNode(t1.val + t2.val)\n",
    "                root.left = self.mergeTrees(t1.left,t2.left)\n",
    "                root.right = self.mergeTrees(t1.right, t2.right)\n",
    "                return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: 'TreeNode', t2: 'TreeNode') -> 'TreeNode':\n",
    "        merge_t1_t2 = TreeNode(None)\n",
    "        if t1 and t2:\n",
    "            merge_t1_t2.val = t1.val+t2.val\n",
    "            merge_t1_t2.left = self.mergeTrees(t1.left, t2.left)\n",
    "            merge_t1_t2.right = self.mergeTrees(t1.right, t2.right) \n",
    "            return merge_t1_t2\n",
    "        elif t1:\n",
    "            merge_t1_t2.val = t1.val\n",
    "            merge_t1_t2.left = self.mergeTrees(t1.left, None)\n",
    "            merge_t1_t2.right = self.mergeTrees(t1.right, None) \n",
    "            return merge_t1_t2\n",
    "        elif t2:\n",
    "            merge_t1_t2.val = t2.val\n",
    "            merge_t1_t2.left = self.mergeTrees(None, t2.left)\n",
    "            merge_t1_t2.right = self.mergeTrees(None, t2.right) \n",
    "            return merge_t1_t2\n",
    "        else:\n",
    "            merge_t1_t2.val = None\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not t1 and not t2:\n",
    "            return []\n",
    "        def mt(node1, node2, t):\n",
    "            rev = 0\n",
    "            if not node1 and not node2:\n",
    "                return\n",
    "            if node1:\n",
    "                rev += node1.val\n",
    "            if node2:\n",
    "                rev += node2.val\n",
    "            t.val = rev\n",
    "            if node1 and node1.left or node2 and node2.left:\n",
    "                t.left = TreeNode(0)\n",
    "                mt(node1.left if node1 else None, node2.left if node2 else None, t.left)\n",
    "            if node1 and node1.right or node2 and node2.right:\n",
    "                t.right = TreeNode(0)\n",
    "                mt(node1.right if node1 else None, node2.right if node2 else None, t.right)\n",
    "            \n",
    "        t = TreeNode(0)        \n",
    "        x = t\n",
    "        mt(t1, t2, t)\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def mmerge(cur1, cur2):\n",
    "            if cur1 == None and cur2 == None: return None\n",
    "            curt = TreeNode(0)\n",
    "            if cur1 != None: curt.val += cur1.val\n",
    "            if cur2 != None: curt.val += cur2.val\n",
    "            curt.left = mmerge(cur1.left if cur1 != None else None, cur2.left if cur2 != None else None)\n",
    "            curt.right = mmerge(cur1.right if cur1 != None else None, cur2.right if cur2 != None else None)\n",
    "            return curt\n",
    "                \n",
    "        return mmerge(t1, t2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1 is None:\n",
    "            return t2\n",
    "        if t2 is None:\n",
    "            return t1\n",
    "        stack1 = [t1]\n",
    "        stack2 = [t2]\n",
    "        i = 0\n",
    "        while i < len(stack1):\n",
    "            if stack1[i] and stack2[i]:\n",
    "                stack1[i].val += stack2[i].val\n",
    "            if stack1[i].left and stack2[i].left:\n",
    "                stack1.append(stack1[i].left)\n",
    "                stack2.append(stack2[i].left)\n",
    "            elif not stack1[i].left:\n",
    "                stack1[i].left = stack2[i].left\n",
    "\n",
    "            if stack1[i].right and stack2[i].right:\n",
    "                stack1.append(stack1[i].right)\n",
    "                stack2.append(stack2[i].right)\n",
    "            elif not stack1[i].right:\n",
    "                stack1[i].right = stack2[i].right\n",
    "            \n",
    "            i+=1\n",
    "        return t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1 and t2:\n",
    "            t1.val += t2.val\n",
    "            t1.left = self.mergeTrees(t1.left, t2.left)\n",
    "            t1.right = self.mergeTrees(t1.right, t2.right)\n",
    "            return t1\n",
    "        return t1 or t2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def recursion_merge(t1,t2):\n",
    "            if t1 is None:\n",
    "                return t2\n",
    "            if t2 is None:\n",
    "                return t1\n",
    "            t1.val += t2.val\n",
    "            t1.left = merge(t1.left,t2.left)\n",
    "            t1.right = merge(t1.right,t2.right)\n",
    "            return t1\n",
    "\n",
    "        def iterative_merge(t1,t2):\n",
    "            if not t1:\n",
    "                return t2\n",
    "            if not t2:\n",
    "                return t1\n",
    "            stack = [(t1,t2)]\n",
    "            while len(stack) > 0:\n",
    "                t = stack.pop(0)\n",
    "                t[0].val += t[1].val\n",
    "                if t[0].left and t[1].left:\n",
    "                    stack.append((t[0].left,t[1].left))\n",
    "                elif (not t[0].left) and t[1].left:\n",
    "                    t[0].left = t[1].left\n",
    "                else:\n",
    "                    pass\n",
    "                if t[0].right and t[1].right:\n",
    "                    stack.append((t[0].right,t[1].right))\n",
    "                elif (not t[0].right) and t[1].right:\n",
    "                    t[0].right = t[1].right\n",
    "                else:\n",
    "                    pass\n",
    "            return t1\n",
    "\n",
    "        return iterative_merge(t1,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def recursion_merge(t1,t2):\n",
    "            if t1 is None:\n",
    "                return t2\n",
    "            if t2 is None:\n",
    "                return t1\n",
    "            t1.val += t2.val\n",
    "            t1.left = merge(t1.left,t2.left)\n",
    "            t1.right = merge(t1.right,t2.right)\n",
    "            return t1\n",
    "\n",
    "        def iterative_merge(t1,t2):\n",
    "            if not t1:\n",
    "                return t2\n",
    "            if not t2:\n",
    "                return t1\n",
    "            stack = [(t1,t2)]\n",
    "            while len(stack) > 0:\n",
    "                t = stack.pop(0)\n",
    "                t[0].val += t[1].val\n",
    "                if t[0].left and t[1].left:\n",
    "                    stack.append((t[0].left,t[1].left))\n",
    "                elif (not t[0].left) and t[1].left:\n",
    "                    t[0].left = t[1].left\n",
    "                else:\n",
    "                    pass\n",
    "                if t[0].right and t[1].right:\n",
    "                    stack.append((t[0].right,t[1].right))\n",
    "                elif (not t[0].right) and t[1].right:\n",
    "                    t[0].right = t[1].right\n",
    "                else:\n",
    "                    pass\n",
    "            return t1\n",
    "\n",
    "        return iterative_merge(t1,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1==None and t2==None:\n",
    "            return None\n",
    "        if t1==None:\n",
    "            return t2\n",
    "        if t2==None:\n",
    "            return t1\n",
    "        arr_1=[t1]\n",
    "        arr_2=[t2]\n",
    "        while len(arr_1)>0 and len(arr_2)>0:\n",
    "            arr_1[0].val+=arr_2[0].val\n",
    "            if arr_1[0].left is not None and arr_2[0].left is not None:\n",
    "                arr_1.append(arr_1[0].left)\n",
    "                arr_2.append(arr_2[0].left)\n",
    "            if arr_1[0].right is not None and arr_2[0].right is not None:\n",
    "                arr_1.append(arr_1[0].right)\n",
    "                arr_2.append(arr_2[0].right)\n",
    "            if arr_1[0].left is None and arr_2[0].left is not None:\n",
    "                arr_1[0].left=arr_2[0].left\n",
    "            if arr_1[0].right is None and arr_2[0].right is not None:\n",
    "                arr_1[0].right=arr_2[0].right\n",
    "            arr_1.pop(0)\n",
    "            arr_2.pop(0)\n",
    "        return t1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if not t1 or not t2:\n",
    "            return t2 if not t1 else t1\n",
    "        queue = [(t1,t2)]\n",
    "        while queue:\n",
    "            r1,r2 = queue.pop()\n",
    "            r1.val += r2.val\n",
    "            if r1.left and r2.left:\n",
    "                queue.append((r1.left,r2.left))\n",
    "            elif not r1.left:\n",
    "                r1.left = r2.left\n",
    "            if r1.right and r2.right:\n",
    "                queue.append((r1.right,r2.right))\n",
    "            elif not r1.right:\n",
    "                r1.right = r2.right\n",
    "        return t1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if not (t1 and t2):\n",
    "            return t1 if t1 else t2\n",
    "        queue = [(t1, t2)]\n",
    "        while queue:\n",
    "            r1, r2 = queue.pop(0)\n",
    "            r1.val += r2.val\n",
    "            if r1.left and r2.left:\n",
    "                queue.append((r1.left, r2.left))\n",
    "            elif not r1.left:\n",
    "                r1.left = r2.left\n",
    "            \n",
    "            if r1.right and r2.right:\n",
    "                queue.append((r1.right, r2.right))\n",
    "            elif not r1.right:\n",
    "                r1.right = r2.right\n",
    "\n",
    "        return t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if not t1 and t2:\n",
    "            return t2\n",
    "        elif t1 and t2:\n",
    "            t1.val = t1.val+t2.val\n",
    "            t1.left = self.mergeTrees(t1.left,t2.left)\n",
    "            t1.right = self.mergeTrees(t1.right,t2.right)\n",
    "        return t1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1 is None or t2 is None:\n",
    "            return t1 or t2\n",
    "        t1.val += t2.val\n",
    "        t1.left = self.mergeTrees(t1.left, t2.left)\n",
    "        t1.right = self.mergeTrees(t1.right, t2.right)\n",
    "        return t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if t1 and t2:\n",
    "            t1.val+=t2.val\n",
    "            t1.left=self.mergeTrees(t1.left,t2.left)\n",
    "            t1.right=self.mergeTrees(t1.right,t2.right)\n",
    "            return t1\n",
    "        return t1 or t2\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        def dfs(t1,t2):\n",
    "           if not (t1 and t2):\n",
    "             return t1 if t1 else t2\n",
    "           t1.val = t1.val + t2.val\n",
    "           t1.left = dfs(t1.left,t2.left)\n",
    "           t1.right = dfs(t1.right, t2.right)\n",
    "           return t1;\n",
    "        return dfs(t1,t2)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "        st = [] \n",
    "        st.append(root1)\n",
    "        st.append(root2)\n",
    "        while st != []:\n",
    "            node2 = st.pop()\n",
    "            node1 = st.pop()\n",
    "            if node1.left and node2.left: \n",
    "                st.append(node1.left)\n",
    "                st.append(node2.left)\n",
    "            if node1.right and node2.right: \n",
    "                st.append(node1.right)\n",
    "                st.append(node2.right)\n",
    "            node1.val += node2.val\n",
    "            if not node1.left and node2.left: \n",
    "                node1.left = node2.left\n",
    "            if not node1.right and node2.right: \n",
    "                node1.right = node2.right\n",
    "        return root1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:\n",
    "        if not root1 and not root2:\n",
    "            return None\n",
    "        elif not root1:\n",
    "            return root2\n",
    "        elif not root2:\n",
    "            return root1\n",
    "\n",
    "        from collections import deque\n",
    "\n",
    "        que = deque([root1, root2])\n",
    "\n",
    "        while que:\n",
    "            temp1 = que.popleft()\n",
    "            temp2 = que.popleft()\n",
    "            temp1.val += temp2.val\n",
    "\n",
    "            if temp1.left and temp2.left:\n",
    "                que.extend([temp1.left, temp2.left])\n",
    "            if temp1.right and temp2.right:\n",
    "                que.extend([temp1.right, temp2.right])\n",
    "\n",
    "            if not temp1.left and temp2.left:\n",
    "                temp1.left = temp2.left\n",
    "            if not temp1.right and temp2.right:\n",
    "                temp1.right = temp2.right\n",
    "\n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1: return root2\n",
    "        if not root2: return root1\n",
    "        from collections import deque\n",
    "        q = deque([root1])\n",
    "        q.append(root2)\n",
    "        while q:\n",
    "            node1 = q.popleft()\n",
    "            node2 = q.popleft()\n",
    "            \n",
    "            if node1.left and node2.left:\n",
    "                q.append(node1.left)\n",
    "                q.append(node2.left)\n",
    "            if node1.right and node2.right:\n",
    "                q.append(node1.right)\n",
    "                q.append(node2.right)\n",
    "\n",
    "            node1.val += node2.val\n",
    "\n",
    "            if not node1.left and node2.left:\n",
    "                node1.left = node2.left\n",
    "            if not node1.right and node2.right:\n",
    "                node1.right = node2.right\n",
    "        \n",
    "        return root1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root1 and not root2: return None\n",
    "        else:\n",
    "            if not root1: return root2\n",
    "            if not root2: return root1\n",
    "\n",
    "        isLeaf = lambda node: not node.left and not node.right\n",
    "        \n",
    "        tree1Que = deque([root1])\n",
    "        tree2Que = deque([root2])\n",
    "        root1.val += root2.val\n",
    "        while tree1Que or tree2Que:\n",
    "            lengthOfLayer = len(tree1Que)\n",
    "            for _ in range(lengthOfLayer):\n",
    "                node1 = tree1Que.popleft()\n",
    "                node2 = tree2Que.popleft()\n",
    "\n",
    "                if isLeaf(node1) and isLeaf(node2):\n",
    "                    continue\n",
    "\n",
    "                if node1.left and node2.left:\n",
    "                    node1.left.val += node2.left.val if node2.left else 0\n",
    "                elif not node1.left and node2.left:\n",
    "                    node1.left = TreeNode(node2.left.val)\n",
    "                if node1.right and node2.right:\n",
    "                    node1.right.val += node2.right.val if node2.right else 0\n",
    "                elif not node1.right and node2.right:\n",
    "                    node1.right = TreeNode(node2.right.val)\n",
    "                \n",
    "                if node1.left and node2.left:\n",
    "                    tree1Que.append(node1.left)\n",
    "                    tree2Que.append(node2.left)\n",
    "                if node1.right and node2.right:\n",
    "                    tree1Que.append(node1.right)\n",
    "                    tree2Que.append(node2.right)\n",
    "        \n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:\n",
    "        # 递归终止条件: \n",
    "        #  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None. \n",
    "        if not root1: \n",
    "            return root2\n",
    "        if not root2: \n",
    "            return root1\n",
    "        # 上面的递归终止条件保证了代码执行到这里root1, root2都非空. \n",
    "        root1.val += root2.val # 中\n",
    "        root1.left = self.mergeTrees(root1.left, root2.left) #左\n",
    "        root1.right = self.mergeTrees(root1.right, root2.right) # 右\n",
    "        \n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def func(root1, root2):\n",
    "            if not root1 or not root2:\n",
    "                return root1 if root1 else root2\n",
    "            root1.val += root2.val\n",
    "            root1.left = func(root1.left, root2.left)\n",
    "            root1.right = func(root1.right, root2.right)\n",
    "            return root1\n",
    "        return func(root1, root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # 如果两个二叉树中，有一个为空，则返回不为空的那个二叉树\n",
    "        if not t1:\n",
    "            return t2\n",
    "        if not t2:\n",
    "            return t1\n",
    "        # 否则将节点的值相加，并递归合并左右子树\n",
    "        merged_tree = TreeNode(t1.val + t2.val)\n",
    "        merged_tree.left = self.mergeTrees(t1.left, t2.left)\n",
    "        merged_tree.right = self.mergeTrees(t1.right, t2.right)\n",
    "        return merged_tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "        queue = [root1, root2]\n",
    "        while queue:\n",
    "            node1 = queue.pop(0)\n",
    "            node2 = queue.pop(0)\n",
    "            if node1.left and node2.left:\n",
    "                queue.append(node1.left)\n",
    "                queue.append(node2.left)\n",
    "            if node1.right and node2.right:\n",
    "                queue.append(node1.right)\n",
    "                queue.append(node2.right)\n",
    "            node1.val += node2.val\n",
    "            if not node1.left and node2.left:\n",
    "                node1.left = node2.left\n",
    "            if not node1.right and node2.right:\n",
    "                node1.right = node2.right\n",
    "\n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "\n",
    "        nodeList1 = collections.deque([root1])\n",
    "        nodeList2 = collections.deque([root2])\n",
    "\n",
    "        while nodeList1:\n",
    "            size1 = len(nodeList1)\n",
    "            for _ in range(size1):\n",
    "                cur1 = nodeList1.popleft()\n",
    "                cur2 = nodeList2.popleft()\n",
    "                cur1.val += cur2.val\n",
    "                if cur1.left:\n",
    "                    nodeList1.append(cur1.left)\n",
    "                    if cur2.left:\n",
    "                        nodeList2.append(cur2.left)\n",
    "                    else:\n",
    "                        nodeList1.pop()\n",
    "                else:\n",
    "                    if cur2.left:\n",
    "                        cur1.left = cur2.left\n",
    "                if cur1.right:\n",
    "                    nodeList1.append(cur1.right)\n",
    "                    if cur2.right:\n",
    "                        nodeList2.append(cur2.right)\n",
    "                    else:\n",
    "                        nodeList1.pop()\n",
    "                else:\n",
    "                    if cur2.right:\n",
    "                        cur1.right = cur2.right\n",
    "        return root1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "        \n",
    "        root = TreeNode(root1.val + root2.val)\n",
    "        queMerge, que = [root], [root1, root2]\n",
    "        while que:\n",
    "            node = queMerge.pop(0)\n",
    "            node1 = que.pop(0)\n",
    "            node2 = que.pop(0)\n",
    "            if node1.left and node2.left:\n",
    "                node.left = TreeNode(node1.left.val + node2.left.val)\n",
    "                queMerge.append(node.left)\n",
    "                que.append(node1.left)\n",
    "                que.append(node2.left)\n",
    "            elif node1.left:\n",
    "                node.left = node1.left\n",
    "            else:\n",
    "                node.left = node2.left\n",
    "            \n",
    "        \n",
    "            if node1.right and node2.right:\n",
    "                node.right = TreeNode(node1.right.val + node2.right.val)\n",
    "                queMerge.append(node.right)\n",
    "                que.append(node1.right)\n",
    "                que.append(node2.right)\n",
    "            elif node1.right:\n",
    "                node.right = node1.right\n",
    "            else:\n",
    "                node.right = node2.right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "        root1.val += root2.val\n",
    "        root1.left = self.mergeTrees(root1.left,root2.left)\n",
    "        root1.right = self.mergeTrees(root1.right,root2.right)\n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1:\n",
    "            return root2\n",
    "        if not root2:\n",
    "            return root1\n",
    "        head = TreeNode(val=root1.val+root2.val)\n",
    "        head.left = self.mergeTrees(root1.left,root2.left)\n",
    "        head.right = self.mergeTrees(root1.right,root2.right)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root1 and not root2:return\n",
    "        if not root1:root1=TreeNode(0)\n",
    "        elif not root2:root2=TreeNode(0)\n",
    "        ans=TreeNode(root1.val+root2.val)\n",
    "        ans.left=self.mergeTrees(root1.left,root2.left)\n",
    "        ans.right=self.mergeTrees(root1.right,root2.right)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
